//package bit1;
//
//import java.util.ArrayList;
//import java.util.LinkedList;
//import java.util.List;
//
//public class home3 {
//    // 子问题思路-求第 k 层结点个数
//    // 查找 val 所在结点，没有找到返回 null
//// 按照 根 -> 左子树 -> 右子树的顺序进行查找
//// 一旦找到，立即返回，不需要继续在其他位置查找
//    List<Integer> res=new ArrayList<>();
//
//    Node find(Node root, int val){
//        res.size();
//        res.get()
//        if(root==null){
//            return null;
//        }
//        if(root.val==val){
//            return root;
//        }
//        Node ret=find(root.left,val);
//        if(ret!=null){
//            return ret;
//        }
//        ret=find(root.right,val);
//        if(ret!=null){
//            return ret;
//        }
//        return null;
//    }
//    int getHeight(Node root){
//        if(root==null){
//            return 0;
//        }
//        int left=getHeight(root.left);
//        int right=getHeight(root.right);
//        if(left<right){
//            return right+1;
//        }
//        return left+1;
//    }
//    int getKLevelSize(Node root,int k){
//        if(root==null||k==0){
//            return 0;
//        }
//        if(k==1){
//            return 1;
//        }
//        return getKLevelSize(root.left,k-1)+getKLevelSize(root.right,k-1);
//
//    }
//    // 遍历思路-求叶子结点个数
//    static int leafSize = 0;
//    void getLeafSize1(Node root){
//        if(root==null){
//            return;
//        }
//        else if(root.left==null&&root.right==null){
//            leafSize++;
//        }
//        else{
//            getLeafSize1(root.left);
//            getLeafSize1(root.right);
//        }
//    }
//    // 子问题思路-求叶子结点个数
//    int getLeafSize2(Node root){
//        if(root==null){
//            return 0;
//        }
//        else if(root.left==null&&root.right==null){
//            return 1;
//        }
//        else {
//            return getLeafSize2(root.left)+getLeafSize2(root.right);
//        }
//    }
//    // 遍历思路-求结点个数
////    static int size = 0;
////    void getSize1(Node root) {
////        if(root==null){
////            return;
////        }
////        else{
////            size++;
////           getSize2(root.left);
////           getSize2(root.right);
////        }
////    }
////    }
////
////    // 子问题思路-求结点个数
////    int getSize2(Node root) {
////        if(root==null){
////            return 0;
////        }
////        else{
////            return getSize2(root.left)+getSize2(root.right)+1;
////        }
////    }
//    List<Integer> list=new LinkedList<>();
//
//}
